%/s\documentclass{cccg11} 
%\usepackage{times}
%\usepackage{url, color, epsfig, amsmath, amsthm, amssymb}
\documentclass{article} 
\usepackage{algorithm}
\usepackage[noend]{algorithmic}
\usepackage{enumerate}
\usepackage{graphicx}
\input mac
\def\L{\ensuremath{\mathcal{L}}}
\def\F{\ensuremath{\mathcal{F}}}
\def\H{\ensuremath{\mathcal{H}}}
\def\R{\ensuremath{\mathcal{R}}}
\def\C{\ensuremath{\mathcal{C}}}
\def\eps{\ensuremath{\epsilon}}
\def\conv{\ensuremath{conv}}
%\newcommand{\remove}[1]{}
\def\polylog{{\mathop{\mathrm{polylog}}\nolimits}}
%\newtheorem{corollary}[theorem]{Corollary}



\newtheorem{theorem}{Theorem}
\newtheorem{invar}{Invariant}	
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{obs}{Observation}
\newtheorem{conj}{Conjecture}
\newtheorem{prop}[theorem]{Proposition}

\def\QED{\ensuremath{{\square}}}
\def\markatright#1{\leavevmode\unskip\nobreak\quad\hspace*{\fill}{#1}}
\newenvironment{proof}
  {\begin{trivlist}\item[\hskip\labelsep{\bf Proof.}]}
  {\markatright{\QED}\end{trivlist}}

\newtheorem{claim}{Claim}
%\newtheorem{observation}{Observation}
%\newtheorem{defi}{Definition}
%\newtheorem{speculation}{Speculation}
\renewcommand{\Re}{\mathbb{R}}
\newcommand{\inprod}[2]{\left\langle #1 , #2 \right\rangle}
%\newsavebox{\smallProofsym}                            
% smallproofsymbol
%\savebox{\smallProofsym}                               %
%\begin{picture}(6,6)                                   %
%\put(0,0){\framebox(6,6){}}                            %
%\put(0,2){\framebox(4,4){}}                            %
%\end{picture}                                          %
%            \fi\fi}
%}   

%----------------------- Macros and Definitions
%--------------------------

% Add all additional macros here, do NOT include any additional files.

% The environments theorem (Theorem), invar (Invariant), lemma
% (Lemma),
% cor (Corollary), obs (Observation), conj (Conjecture), and prop
% (Proposition) are already defined in the cccg08.cls file.
% Add additional environments only if you REALLY need them.

\newcommand{\qed}{\vrule height8pt width8pt depth4pt}
\def\qedbox{\vrule width 0.61em depth 0.12em height 0.49em}
\def\qed {\ifinner \noalign {\global\dimen1=\prevdepth
\ifdim\prevdepth=-1000pt \global\dimen1=0pt \fi
\vskip-\dimen1 \nointerlineskip}
\omit\span\omit \hfil
\vbox to -\dimen1{\vss
    \hbox to 0pt{\hss \hbox to \hsize{\hfill\qedbox}\hss}}\hfil\crcr
 funktionirt auch in \eqalign (nach dem letzten \cr)
\else \ifmmode \eqno\qedbox
       \else \qquad\hbox{}\nobreak\hfill \nopagebreak \qedbox\par \smallskip
            \fi\fi}
%----------------------- Title
%-------------------------------------------


\title{We Will Have a Great Title} 
\author{Nabil Mustafa\thanks{Deptartment. of Computer Science, LUMS,
Pakistan, nabil@lums.edu.pk}, Saurabh Ray\thanks{Inst. of Maths.,EPFL,
Switzerland, suarabh.ray@epfl.ch}, M. Shabbir\thanks{Deptartment of Computer
Science, Rutgers, mudassir@cs.rutgers.edu}, William
Steiger\thanks{Deptartment of Computer Science, Rutgers,
steiger@cs.rutgers.edu}} 
%\index{Mustafa, N.} \index{Ray, S.} \index{Shabbir, M.}
 %\index{Steiger, W.}
\begin{document}
\thispagestyle{empty}

\maketitle
\begin{abstract}

In this paper, we introduce some new algorithms for the notion of
\em{Ray Shooting Depth} for any set $P$ of $n$ points in $R^2$. 
\end{abstract} 

\bigskip

\section{Introduction}

\label{sec:intro}

]bigskip

For discussion below, $\rho(q,P)$ represents RS Depth of a point $q$
with repsect to some pointset $P$ in plane. We give simple algorithms
to show that

\begin{theorem}

\label{thm1}

Given a set $P$, and a query point $q$, $\delta(q,P)$ can be computed
in time $\Theta(n log n)$, where $|P|=n$.

\end{theorem}

\begin{theorem}

\label{thm2}

Given two set $P$ and $Q$ such that $|P|=n, |Q|=m$, RS depth
$\delta(q_i,P), \forall q_i\in Q$ can be computed in time
$O(n^2+m^2)$.

\end{theorem}

\begin{theorem}

\label{thm3}

RS depth of all \emph{combinatorial} points in plane w.r.t a given a
set $P$ can be computed in time $O(n^4)$.

\end{theorem}

Also

\begin{theorem}

\label{thm4}

Given a set $P$, let $q\in \R^2$ s.t. $\delta(q,P)\geq
\delta(q\prime,P), \forall q\prime \in \R^2$, then $q$ can be computed
in time $O(n^4)$.

\end{theorem}

\begin{theorem}

\label{thm5}

Given a set $P$, let $q\in \R^2$ s.t. $\delta(q,P)\geq
\delta(q\prime,P), \forall q\prime \in P$, then $q$ can be computed in
$O(n^2)$.

\end{theorem}

We give a lower bound to show that result in Theorem~\ref{thm1} is
tight. Also the claim in Theorem~\ref{thm3} is optimal as well. 


We follow these theoretical results with simple and easily portable
implementations. Particularly we discuss $RSplot$, a new bivariate
data visualization tool that we developed based on Ray Shooting
algorithms. Software we developed are open source and freely available
in R, the standarad statistical development environment. 

We also conducted an experimental study to compare accuracy and
robustness of RS depth with already known data depth measures Tukey,
Simplicial, Oja, and Spatial medians on relatively large data sets
chosen randomly from eleven different distributions. We discuss
details of our method and results for this simulation in the last
section.

\section{Algorithms}

\label{sec:algos}

Given two sets $P$ and $Q$ in plane, such that $|P| = n, |Q| = m$ , we
give following algorithm to compute RS Depth, $\eta(P, q_i), \forall
q_i\in Q$. We abuse following notations for the discussion below: $(a,
b)$ to mean a line passing through, and $[a, b]$ to mean a line
segment through points

$a, b$ and $[a, b)$ to mean a half infinite ray starting at $a$ and
passing through $b$. Also for a point $p\in R^2$, its dual line is
denoted by $p^*$; we do not fix any point line duality, and any
definition that preserves incidence and above/below relationship will
suffice.

\begin{algorithm}                      

\caption{RS Depth of $|Q|=m$ with respect to $|P|=n$}   

\label{alg1} 

\begin{algorithmic}

\STATE build $\mathcal{A}(P)$, the arrangment of $p_i^*$ for $p_i\in
P$
\FORALL{$q_i \in Q$}
	\STATE $L_i\gets \{l_{i,j}:$ slope of $(q_i,p_j) \}$
	\STATE sort $L_i$ by inserting $q_i^*$ in
	$\mathcal{A}(P)$. W.L.O.G. $l_{i,1}\leq l_{i,2}\ldots \leq
	l_{i,n}$ be in anti-clockwise order on unit circle with $q_i$
	as center. Also $p_{i,j}\in P$ be alias of a point with which
	makes slope $l_{i,j}$ with $q_i$.
\ENDFOR
\STATE \textbf{end for}
\FORALL{$q_i \in Q$}
	\STATE $arc_{i,j}\gets $ number of points as we walk from
	$p_{i,j}$ to $-p_{i,j}$.
	\STATE $\eta_{i,1}\gets \sum_{k=1}^n(n-arc_{i,k}-k-1)$	

	\FOR{$r = 2 \to n$}

			\STATE $\eta_{i,r}\gets  \eta_{i,r} - n + 2
			\times arc_{i,j-1}+1)$			

	\ENDFOR

	\STATE \textbf{end for}

	\STATE $\eta_i \gets \min_{j=1}^n \eta_{i,j}$

\ENDFOR

\STATE \textbf{end for}

\RETURN $\eta$

\end{algorithmic}

\end{algorithm}  

\subsection{Algorithm to compute RS-Median of a Pointset}

Given a set $P$ of $n$ points in plane, we give an algorithm to
compute RS-Depth of all points in plane, also locate an arbitrary
point $z$ such that $\delta(z)\geq \delta(z\prime), \forall
z\prime\in\R^2 $. 

We divide plane into a set of faces defined by the arrangemnt
$\mathcal{A}(E_P)$, of $ {n\choose 2}$ lines induced on points in
$P$. We observe that all points within a face have same RS-Depth, and
also we note a relation between $\delta$ values of $delta$ values of
points in neighboring faces. We define $N(f_i, P)$ as set

of all neighbor faces of face $f_i$ where two faces are neighbors to
each other if they share a common edge. $N(f_i) = N(f_i, P)$ where $P$
is obvious from the context. We fix $f_0$ to be the unbounded face of
this arrangment which is rather a union of all unbounded faces but we
will use it just one face whose description is readily available by
taking the convex hull of $P$. Algorithm follows:

\begin{algorithm}                      

\caption{RS Median of a set $|P|=n$}   

\label{alg2} 

\begin{algorithmic}

\STATE build $\mathcal{A}(E_P)$, the arrangment of $(p_i,p_j)\in
P\times P$

\STATE Let $F=$ set of all faces in $\mathcal{A}(E_P)$.

\FORALL{$f_i \in F$}

	\STATE $label(f_i)\gets \infty$

\ENDFOR

\STATE \textbf{end for}

\STATE $count \gets 0$

\STATE $label(f_i)\gets count$

\STATE $\L \gets \{f_i\} $

\STATE $S\gets \L$

\REPEAT

\STATE $R\gets S$

\STATE $S\gets \emptyset$

\STATE $count \gets count +1 $

\FORALL{$l_i \in \L$}

	\STATE Remove $l_i$ from $\L$

	\FORALL{$f_j \in N(l_i), s.t. label(f_j) = \infty $}

		\STATE $label(f_j) \gets count $

		\STATE $S\gets S\cup \{f_j\}$		
	\ENDFOR

	\STATE \textbf{end for}
\ENDFOR
\STATE \textbf{end for}
\STATE $\L \gets S $

\UNTIL{ $\L = \emptyset$ }

\RETURN $R$ as set of RS-Median points.

\end{algorithmic}

\end{algorithm}  


\begin{lemma}

For any two points $x,y$ in some $f_i$, $\delta(x)=\delta(y)$ always
holds.

\end{lemma}

\begin{lemma}

Its easy to see that complexity of algorithm is linear in number of all neighbors of all faces. Number of neighbors of each face is equal to number of line segments the face is defined on. Since each such segment is counted exactly twice in this quantity, number of all neighbors of all faces is equal to twice the number of segment. By planaity of graph it follows from Euler fromula that this is linear in terms of number crossing points which is $O(n^4)$.

\end{lemma}


\subsection{Lower bound on computing RS-Depth of a point}

In this section we prove $\Omega(n log n)$ lower bound on algorithm
computing RS-Depth of a query point $q$ for a n-pointset $P \in \R^2$
in algebraic computation tree model. We provide a linear time
reduction from set-equality problem: Given two sets $A =
\{x_1,x_2,\ldots,x_n\}$ and $B = \{y_1,y_2,\ldots,y_n\}$ in $R$, it
takes $\Omega(n log n)$ computations to decide whether or not $A = B$.

\begin{lemma}
Any algebraic computation tree that solves $n$-points RS-Depth problem
 has a complexity $\Omega(n log n)$
\end{lemma}

\noindent
{\bf Proof:} 
Given two sets $A = \{x_1,x_2,\ldots,x_n\}$ and $B =
\{y_1,y_2,\ldots,y_n\}$ we construct $P \in \R^2$, such that by
finding out depth of origin $w.r.t P$ we will be able to decide
$A=B?$. First, without loss of generality we assume that
$0<x_i<\frac{\pi}{2}, \forall x_i\in A$, if not we know that a mapping
always exists. Similarly $0<y_i<\frac{\pi}{2}, \forall y_i\in B$. Now
for each $x_i\in A$ we define $p_i=(\frac{i}{n},cos(x_i))$, and for
each $y_j\in B$, $p_{n+j}=(-\frac{j}{n},cos(y_j+\frac{\pi}{2}))$. We
claim.
\begin{claim}

\label{claim1}

If $\delta(O)=\frac{n^2}{8}$ for set $P=\{p_1,p_2,\ldots,p_{2n}\}$,
where $O=(0,0)$, then $A=B$.

\end{claim}

\noindent
{\bf Proof:}
Let us suppose otherwise that $A \neq B$, and W.L.O.G. $x_1\leq
x_2\ldots \leq x_n$ and $y_1\leq y_2\ldots \leq y_n$ and let $i$ be
smallest such that $x_i<y_i$. By our construction it implies that
$p_i\neq p_{n+i}$. Now consider the line $l$ passing through $O$ such
that both 

 Consider the line passing through $O$ s.t. both $p_i, p_{n+i}$ lie to
 the right of it and points $p_{i+1},p_{i+2}\ldots,p_{n}$ are on
 left. We see that $(\frac{n}{2}-1).(\frac{n}{2}+1)$ line segments
 induced on $P$ intersect this line, hence at least one of the two
 rays in $l$ starting at $O$ intersects at most $\frac{n^2}{8}-1$ line
 segments contradicting the assumption that $\delta(O)=\frac{n^2}{8}$.
\qed

\begin{claim}

\label{claim2}

If $\delta(O)<\frac{n^2}{8}$ for set $P=\{p_1,p_2,\ldots,p_{2n}\}$,
where $O=(0,0)$, then $A\neq B$.

\end{claim}

\noindent
{\bf proof}

Again assume $A=B$. By construction of $P$, we note that for any
$p_i\in P$, there is exactly one antipodal point $p_j\in
P$. Furthermore any line $l$ passing through $O$ is a halving line of
$P$: both half-planes such defined have exactly $\frac{n}{2}$ points
(unless $l$ passes through some $p_i$ which we discuss later). So
$\frac{n^2}{4}$ line segments intersect each line, and as points are
arranged symmetrically around $O$ in first and third quadrants of
plane, both half infinite rays of such $l$ starting at $O$ intersect
equal number of line segments.

In case of a line passing through two antipodal points in $P$, line
intersects $(\frac{n}{2}-1)^2.(n-1)$ segments and each ray intersects
at least $\frac{n^2}{8}+\frac{n-1}{2}$ line segments. This contradicts
the assumption that $\delta(O)<\frac{n^2}{8}$ implying $A\neq B$.\qed

Claim~\ref{claim1} and Claim~\ref{claim2} complete the reduction by
showing that computing RS Depth of set of $n$ points in plane, we can
decide set equality. Lower bound follows.\qed

\section{RSplot: A Bivaruate Data Visulization Tool}

Given remarkable accuracy of Ray Shooting depth to rank points in plane, as observed in Simulations section below, its natural to consider it for purpose of bivariate data representation and outlier identification.

We implemented RSplot, in R, the standard statistical computing language so that it is readily available to use and extend on all recognised palteforms. As we also provide its source in C++, it can easily be ported to other environment. R package for current implementation is available on all R CRAN servers and link to main repositorty is \emph{http://cran.r-project.org/web/packages/rsdepth/}. Some examples where RSplot is used to represent some real world data follow:

\subsection{Motivations for RSplot}

We provide three interfaces for all the functionality
\subsection{RSplot Interfaces}
To provide all the promised functionality, RSplot exposes a number of interfaces in main RSdepth package. A brief usage, variations, requirements, examples and implemenation details of each interface follows.

\subsubsection{rsrings: contours of rs-depths}

Given a two dimensional matrix of a bivariate sample $P$, \emph{rsrings} creates a plot of data, identifies a point in $P$ as deepest point, and divides $P$ into a set of five convex contours or rings of gradually increasing sizes. Each ring contains 20\% more points than the next smaller ring, and smaller rings signify a deeper set of points with high RS depth. Interface provides a way to change to number of rings to be generated, fraction of points in each ring changes accordingly. Contours can optionally be made colorful.
We observed that, while rsrings may give a successful plot in any case, for rings to be provide any meaningful information it is a good that number of rings be less than $\frac{n}{50}$ and more than $3$.
\emph{rsrings} gives a visual description of centrality ranking of points and perfect for a study of bivarate Spacings. Below we used it on three sets of $500$ points each drawn respectively from bivariate uniform, bivariate normal and bivariate exponential distributions at random. Please observe that in all cases rings drawn provide a near optimal estimate of underlying distribution. 

To construct these rings, we 
\begin{itemize}	
	\item Sort points in $P$ according to their RS depth
	\item Partition sorted $P$ into blocks of appropriate sizes, of size $\frac{n}{5}$ by default.
	\item Take convex hull of each part part.
	\item And find the median point.
\end{itemize}

%\TODO: replace rsrings with some code

While we gave an $O(n^2)$ algorithm for constructing {rsrings}, we used a simpler $O(n^2 \log{n})$ approach. Thats because we could not find any efficient implementaiton of line arrangement; hidden constant for line arrangement in {CGAL} library is too high that for all data sets of sizes less than $10000$, its more feasible to use our current implementation. We also note that relative to other similar software in statistics development environments, our implementaiton is quite efficient for practical purposes, for example, it took less than $3$ seconds to figure out and draw $100$ rings on a set of $500$ points on 2GHz Intel processor. A well known implementation that uses Tukey median to draw contours, took more than a minute on same set of points on same machine. Unfortunateley we could not find any open source implemention of drawing contours of Simplicial depth.

\subsubsection{rstruerings: ``true'' contours of rsdepth}

{rstruerings} also generates contours based rsdepth, but unlike {rsrings}, all points within a contour, including points that are not in sample, fall in same range of rsdepth. It gives a more fine grained ranking of points with repsect to rsdepth. This makes more sense for some particular types of samples: for example given a smaple $P$, such that all points in $P$ are in convex positions, there is essentially a single contour based on $rsrings$ because all points in $P$ have same rank according to centrality. But if we use $rstruerings$, we can still get $O(n^2)$ meaningful rings or contours. So, although {rsrings} give a more appopriate picture of the underlying distribution, it is sometimes more relevant to visual the ``true'' contours based on RS depth of all points in plane (not just the points from sample $P$) for it has different geometric structure. 

It is a strictly harder computaitonal problem and compared to $O(n^2)$ algorithm for constructing {rsrings}, there is, as observed above, an $\Omega(n^4)$ on time complexity of constructing {$rstruerings$}.



\subsubsection{rsplot: a Bagplot with rsdepth}

We present {rsplot}, a variant of Bagplot, using Ray Shooting depth instead of Tukey depth. Main components of RSplot include:

\begin{itemize}
	\item RS median point: a point of maximum RS depth.
	\item Median bag: convex hull of set of all median points. 
	\item Half bag: a convex polygon that contains 50\% points in $P$.
	\item Fence: a polygon that identifies outliers in data from inliers.
\end{itemize}

Below we show few applications of {rsplot} on plasma readings of $60$ patients. Plot on left is, an approximate one, where Half bag is constructed by the convex hull of $\frac{n}{2}$ deepest points with respect to their rsdepth.

%\twocolumn

%TODO: add reference for the data


\subsubsection{rstinterval: a tolerance interval of rsdepth}
Tolerance internval is distinct from a confidence internval, and is define in \ref{liu08} as below:


$T(X_1, \ldots ,X_n)$ is called a $\beta$-expectation tolerance interval
(or region) if
 if
\[
E( P_F(T(X_1, \ldots ,X_n)) ) = \beta
\]

where $X_1, \ldots ,X_n$ is a random sample of size $n$ from some distribution $F$. We give a robust implementation of their
method to approximate tolerance regions in $R^2$. Bellow is an example where we approximate a set of $10000$ points from normal 
distribution.




\section{Simulations}

\label{section:simulations}

\subsection{Data Source and their Sizes}

\label{sec:data}

For our experiments we choose bivariate data points randomly from a
set different distributions. This set includes a mixture of uniform,
centrally concentrated, and heavy-tailed distributions to give a
better idea of performance of various median estimators and data depth
function. We also choose a set of contaminated distributions, as
described below, to measure effect of outliers on these estimations. Here are steps of 

\begin{enumerate}[Step i --]
\item choose a set of 5000 points in plane at random from each
of these distributions as our actual set of points, we call $P$.
\item choose five samples of 45 points each uniformly from $P$
\item for eah sample calculate median with respect to particular depth measure
\item take the point of highest depth among five points thus calculated as approximate median.
\end{enumerate}

Each experiment was replicated 500 times, and averaged out results
were used to minimize errors in approximation. For four median measure 
to compute median in $Step (iii)$, and twelve distributions to choose from in $Step (i)$,
we get $12 \times 4\times 500=18,000$ observations in total. Depth measures are 1)\emph{RS depth}, 2) \emph{Tukey depth}
3)\emph{Simplicial depth}, and 4)\emph{Oja depth}.

Six pure distributions are as follow:

\begin{enumerate}

\item Normal with $ \tilde{x} = 0 $
\item Uniform with $\tilde{x} = 0 $
\item Cauchy with $\tilde{x} = 0 $
\item Exonential with $\tilde{x} = 0.693147181$
%TODO: fix median of F distribution
\item F distribution with $\tilde{x} = 0.98$, $df_1 = 100$ and
$df_2 = 100$
\item t Student distribution with $\tilde{x} = 0$, $df = 5$
\end{enumerate} 
where $\tilde{x}$ represents the median of a distribution. Six contaminated distributions are
\begin{enumerate}

\setcounter{enumi}{+5}

\item Normal with 5\% contamination from Normal with a
displaced mean.

\item Normal with 10\% contamination from Normal with a
displaced mean.

\item Normal with 30\% contamination from Normal with a
displaced mean.

\item Cauchy with 5\% contamination from Normal with a
displaced mean.

\item Cauchy with 10\% contamination from Normal with a
displaced mean.

\item Cauchy with 30\% contamination from Normal with a
displaced mean.
\end{enumerate}

\subsection{Measure of Performance}

We quantify accuracy, biasness and robustness of four median estimator, described above, according to two standard
measures of point estimators. Mean Squared Error $MSE$, is a precision quantifier and for our simulations, is defined as
numerical function of estimated and true value as below:
\begin{equation}
\label{eq:RMSE}
MSE(\hat{\theta},\theta) = {MSE(\hat{\theta},\theta)} = {\frac{1}{500} \sum_{i=1}^{500} \mathbf{E}((\hat{\theta}_i-\theta)^2)}
\end{equation}

where $\hat{\theta}_i$ takes the value of median estimators, and
${\theta}$ is actual mean of the distribution to be test. 

Second estimator for the accuracy is squared bias of estimators,
which is a relation between $MSE$ and variance, and is given as below as below:
\begin{equation}
\label{eq:Bias}
  \left( Bias(\hat{\theta},\theta) \right)^2 =  {\frac{1}{500} \sum_{i=1}^{500} \mathbf{E}((\hat{\theta}_i-\theta))}
\end{equation}

Both of these measures give an account of the accuracy of a particular
estimator: smaller value of \ref{eq:RMSE} and \ref{eq:Bias} is an
indicator of better estimator. 

\subsection{Algorithms}

\label{sec:algorithms}

Following algorithms were employed for this study.


\begin{itemize}

\item \textbf{RS depth :} For rsdepth we use simple $O(n log n)$
algorithm: that is to sort all points in data set radially around
query point, and calculate number of segments interesting a particular
ray. As given depth in particular ray, depth in neighboring rays can
be found in constant time, linear time is enough to find least ray
depth. If depths of two points is equal, we pick arbitrarily. C++/R
implementation of algorithm was used from $RSdepth$ package in R.

\item \textbf{Tukey depth :} calculation of Tukey Depth is based on
Fortran code from Rousseeuw and Ruts (1996) available in R as $depth$
package.

\item \textbf{Simplicial depth :} calculation of Simplicial or Liu
depth is again based on Fortran code from Rousseeuw and Ruts (1996)
available in R as $depth$ package.

\item \textbf{Oja depth :} is derived from a location measure
considered by Oja. Implementation comes from $depth$ package in R.

\end{itemize} 

We assume that all these median estimators try to approximate median of
the distributions that we used. Furthermore we expect a robust
estimator to behave well even in case when mean has been dragged in
some arbitrary direction due to a ``certain amount of erroneous
data''. 

Functions to generate random number generation for all our
distributions that we used were borrowed from R base packages. We used
internal R language environment to implement rest of the algorithm and
run experiment scripts. $RSdepth$ package that we wrote to conduct
this study is now available in main R CRAN repository along with its
C++ source code \cite{rsdepth_repos}.

\subsection{Results}

Results of our experiments follow in ten tables at the end of this
section, one for each distribution used as source of data set; two
rows in each table represent tested median approximator's value for
$MSE$ and $Bias^2$. Our interpretation of these results follow:


\begin{table}[h]

\begin{center}

\begin{tabular}{rp{1.2cm}p{1.2cm}p{1.2cm}p{1.2cm}}
  \hline
 & rs & tukey & simplicial & oja \\ 
      \hline
 1 & 0.50354 & 0.47624 & 0.50543 & 0.50247 \\ 
  2 & 0.70728 & 0.67044 & 0.70663 & 0.70656 \\ 
   \hline
\end{tabular}
\caption{Standard Uniform distribution}

\end{center}

\end{table}

\begin{table}[h]

\label{table:2}

\begin{center}

\begin{tabular}{rp{1.2cm}p{1.2cm}p{1.2cm}p{1.2cm}}
  \hline
1 & 0.05694 & 0.05616 & 0.10046 & 0.05710 \\ 
  2 & 0.21102 & 0.20649 & 0.28361 & 0.21129 \\ 
   \hline
\end{tabular}
\caption{Standard Normal distribution}

\end{center}
\end{table}
\begin{table}[h]
\begin{center}
\begin{tabular}{rp{1.2cm}p{1.2cm}p{1.2cm}p{1.2cm}}

  \hline
 & rs & tukey & simplicial & oja \\ 
      \hline
1 & 0.14163 & 0.12955 & 0.21941 & 0.12613 \\ 
  2 & 0.32732 & 0.29979 & 0.40272 & 0.30881 \\ 
   \hline
\end{tabular}
\caption{Cauchy distribution}
\end{center}
\end{table}

%with mean=0.98
\begin{table}[h]
\begin{center}
\begin{tabular}{rp{1.2cm}p{1.2cm}p{1.2cm}p{1.2cm}}
  \hline
  & rs & tukey & simplicial & oja \\ 
    \hline
1 & 0.00381 & 0.09962 & 0.00577 & 0.00379 \\ 
  2 & 0.05563 & 0.12167 & 0.06679 & 0.05545 \\ 
   \hline
\end{tabular}
\caption{Fisher distribution}
\end{center}
\end{table}

%with mean=1
\begin{table}[ht]
\begin{center}
\begin{tabular}{rp{1.2cm}p{1.2cm}p{1.2cm}p{1.2cm}}
  \hline
 & rs & tukey & simplicial & oja \\ 
      \hline
1 & 0.05978 & 0.09527 & 0.09890 & 0.05628 \\ 
  2 & 0.21224 & 0.24385 & 0.27090 & 0.20504 \\ 
   \hline
\end{tabular}
\caption{Exponential distribution}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{rp{1.2cm}p{1.2cm}p{1.2cm}p{1.2cm}}
  \hline
 & rs & tukey & simplicial & oja \\ 
      \hline
1 & 0.06677 & 0.06430 & 0.11946 & 0.06649 \\ 
  2 & 0.22956 & 0.21788 & 0.30526 & 0.22859 \\ 
   \hline
\end{tabular}
\caption{Student t distribution}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{rp{1.2cm}p{1.2cm}p{1.2cm}p{1.2cm}}
  \hline
 & rs & tukey & simplicial & oja \\ 
      \hline
1 & 0.07043 & 0.06645 & 0.10843 & 0.07029 \\ 
  2 & 0.23302 & 0.22090 & 0.28928 & 0.23285 \\ 
   \hline
\end{tabular}
\caption{Normal Distribution contaminated with 5\% Normal}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{rp{1.2cm}p{1.2cm}p{1.2cm}p{1.2cm}}
  \hline
 & rs & tukey & simplicial & oja \\ 
     \hline
1 & 0.11724 & 0.10966 & 0.16649 & 0.11976 \\ 
  2 & 0.30006 & 0.27865 & 0.35095 & 0.30316 \\ 
   \hline
\end{tabular}
\caption{Normal Distribution contaminated with 10\% Normal}
\end{center}
\end{table}


\begin{table}
\begin{center}
\begin{tabular}{rp{1.2cm}p{1.2cm}p{1.2cm}p{1.2cm}}

  \hline
 & rs & tukey & simplicial & oja \\ 
      \hline
1 & 1.74510 & 1.50682 & 1.43463 & 1.66417 \\ 
  2 & 1.11991 & 0.96901 & 0.98668 & 1.11343 \\ 
   \hline
\end{tabular}
\caption{Normal Distribution contaminated with 30\% Normal}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{rp{1.2cm}p{1.2cm}p{1.2cm}p{1.2cm}}
  \hline
 & rs & tukey & simplicial & oja \\ 
      \hline
1 & 0.19712 & 0.17455 & 0.27485 & 0.17496 \\ 
  2 & 0.38412 & 0.34719 & 0.45147 & 0.35990 \\ 
   \hline
\end{tabular}
\caption{Cauchy Distribution contaminated with 5\% Normal}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{rp{1.2cm}p{1.2cm}p{1.2cm}p{1.2cm}}
  \hline
 & rs & tukey & simplicial & oja \\ 
  \hline
1 & 0.28070 & 0.25844 & 0.35918 & 0.24860 \\ 
  2 & 0.46333 & 0.42668 & 0.51551 & 0.43616 \\ 
   \hline

\end{tabular}
\caption{Cauchy Distribution contaminated with 10\% Normal}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{rp{1.2cm}p{1.2cm}p{1.2cm}p{1.2cm}}

  \hline
 & rs & tukey & simplicial & oja \\ 
      \hline
1 & 4.75113 & 4.93386 & 4.71630 & 3.55947 \\ 
  2 & 1.86559 & 1.86767 & 1.63743 & 1.58556 \\ 
   \hline

\end{tabular}
\caption{Cauchy Distribution contaminated with 30\% Normal}
\end{center}
\end{table}

\newpage

%\bibliographystyle{plain}	% (uses file "plain.bst")
%\bibliography{r2}

\end{document}

